{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #最长的斐波那契子序列的长度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lenLongestFibSubseq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长的斐波那契子序列的长度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果序列&nbsp;<code>X_1, X_2, ..., X_n</code>&nbsp;满足下列条件，就说它是&nbsp;<em>斐波那契式&nbsp;</em>的：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n &gt;= 3</code></li>\n",
    "\t<li>对于所有&nbsp;<code>i + 2 &lt;= n</code>，都有&nbsp;<code>X_i + X_{i+1} = X_{i+2}</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>给定一个<strong>严格递增</strong>的正整数数组形成序列 <code>arr</code>&nbsp;，找到 <code>arr</code> 中最长的斐波那契式的子序列的长度。如果一个不存在，返回&nbsp;&nbsp;0 。</p>\n",
    "\n",
    "<p><em>（回想一下，子序列是从原序列&nbsp; <code>arr</code> 中派生出来的，它从 <code>arr</code> 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如，&nbsp;<code>[3, 5, 8]</code>&nbsp;是&nbsp;<code>[3, 4, 5, 6, 7, 8]</code>&nbsp;的一个子序列）</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>arr =<strong> </strong>[1,2,3,4,5,6,7,8]\n",
    "<strong>输出: </strong>5\n",
    "<strong>解释: </strong>最长的斐波那契式子序列为 [1,2,3,5,8] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>arr =<strong> </strong>[1,3,7,11,12,14,18]\n",
    "<strong>输出: </strong>3\n",
    "<strong>解释</strong>: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= arr.length &lt;= 1000</code></li>\n",
    "\t<li>\n",
    "\t<p><code>1 &lt;= arr[i] &lt; arr[i + 1] &lt;= 10^9</code></p>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 873&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence/\">https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [Q91FMA](https://leetcode.cn/problems/Q91FMA/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [Q91FMA](https://leetcode.cn/problems/Q91FMA/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6,7,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "         # 将数组转换为集合，以便进行快速查找\n",
    "        s = set(arr)\n",
    "        \n",
    "        # 数组的长度\n",
    "        n = len(arr)\n",
    "        \n",
    "        # 初始化最长斐波那契子序列的长度\n",
    "        ans = 0\n",
    "        lst = []\n",
    "        # 遍历数组的每个元素\n",
    "        for i in range(n):\n",
    "            \n",
    "            # 遍历当前元素之后的每个元素\n",
    "            for j in range(i + 1, n):\n",
    "                # 初始化当前斐波那契序列的前两个元素\n",
    "                x, y = arr[j], arr[j] + arr[i]\n",
    "                l = [arr[i],arr[j]]\n",
    "                # 初始化当前斐波那契序列的长度\n",
    "                length = 2\n",
    "                # 检查下一个元素是否在数组中\n",
    "                while y in s:\n",
    "                    # 更新斐波那契序列的长度                \n",
    "                    length += 1\n",
    "                    l.append(y)\n",
    "                    # 更新斐波那契序列的前两个元素\n",
    "                    x, y = y, x + y\n",
    "                # 更新最长斐波那契子序列的长度\n",
    "                # if length > ans: lst = l\n",
    "                lst =l if length > ans else lst\n",
    "                ans = max(length, ans)  \n",
    "                \n",
    "        # 如果最长斐波那契子序列的长度大于等于3，则返回该长度，否则返回0\n",
    "        return ans if ans >= 3 else 0  # lst 返回最长子序列\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "         # 将数组转换为集合，以便进行快速查找\n",
    "        s = set(arr)\n",
    "        \n",
    "        # 数组的长度\n",
    "        n = len(arr)\n",
    "        \n",
    "        # 初始化最长斐波那契子序列的长度\n",
    "        ans = 0\n",
    "        \n",
    "        # 遍历数组的每个元素\n",
    "        for i in range(n):\n",
    "            # 遍历当前元素之后的每个元素\n",
    "            for j in range(i + 1, n):\n",
    "                # 初始化当前斐波那契序列的前两个元素\n",
    "                x, y = arr[j], arr[j] + arr[i]\n",
    "                \n",
    "                # 初始化当前斐波那契序列的长度\n",
    "                length = 2\n",
    "                \n",
    "                # 检查下一个元素是否在数组中\n",
    "                while y in s:\n",
    "                    # 更新斐波那契序列的长度\n",
    "                    length += 1\n",
    "                    \n",
    "                    # 更新斐波那契序列的前两个元素\n",
    "                    x, y = y, x + y\n",
    "                \n",
    "                # 更新最长斐波那契子序列的长度\n",
    "                ans = max(length, ans)  \n",
    "        \n",
    "        # 如果最长斐波那契子序列的长度大于等于3，则返回该长度，否则返回0\n",
    "        return ans if ans >= 3 else 0 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        arr_dict = {i: j for j, i in enumerate(arr)}\n",
    "        if len(arr) <= 2:\n",
    "            return 0\n",
    "        max_len = 0\n",
    "        n = len(arr)\n",
    "        for i in range(len(arr)-1):\n",
    "            list_res = []\n",
    "            for j in range(i+1, n):\n",
    "                a, b = arr[i], arr[j]\n",
    "                cur_len = 0\n",
    "                if a + b in arr_dict:\n",
    "                    cur_len = 3\n",
    "                    a, b = b, a+b\n",
    "                    while a + b in arr_dict:\n",
    "                        cur_len += 1\n",
    "                        a, b = b, a+b\n",
    "                max_len = max(max_len, cur_len)\n",
    "\n",
    "        return max_len\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        arr_set = set(arr)\n",
    "        max_len = 0\n",
    "        dp = [{}, {}]\n",
    "        for i in range(2, len(arr)):\n",
    "            temp = {}\n",
    "            for j in range(i - 1, 0, -1):\n",
    "                if arr[i] - arr[j] in arr_set and arr[j] > arr[i] - arr[j]:\n",
    "                    temp[arr[j]] = 3\n",
    "                    max_len = max(max_len, 3)\n",
    "                for k in dp[j]:\n",
    "                    if arr[i] == arr[j] + k:\n",
    "                        temp[arr[j]] = dp[j][k] + 1\n",
    "                        max_len = max(max_len, temp[arr[j]])\n",
    "            dp.append(temp)\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        arr_set = set(arr)\n",
    "\n",
    "        dp = {}\n",
    "        for k in range(1, n):\n",
    "            c = arr[k]\n",
    "            for j in range(k-1, -1, -1):\n",
    "                b = arr[j]\n",
    "                a = c - b\n",
    "                if a >= b:\n",
    "                    break\n",
    "                if a in arr_set:\n",
    "                    dp[(b, c)] = dp.get((a, b), 2) + 1\n",
    "        if not dp:\n",
    "            return 0\n",
    "        return max(dp.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        cache = [[] for i in range(len(arr))]\n",
    "        maxi = 0\n",
    "        for i in range(2, len(arr)):\n",
    "            key = arr[i]\n",
    "            ph = 0\n",
    "            pl = i-1\n",
    "            for j in range(i):\n",
    "                if arr[ph] + arr[pl] == key:\n",
    "                    flag = True\n",
    "                    for l in range(len(cache[pl])):\n",
    "                        if cache[pl][l][0] == arr[ph]:\n",
    "                            cache[i].append([arr[pl], cache[pl][l][1]+1])\n",
    "                            maxi = max(maxi, cache[pl][l][1]+1)\n",
    "                            flag = False\n",
    "                            break\n",
    "                    if flag:\n",
    "                        cache[i].append([arr[pl], 3])\n",
    "                        maxi = max(maxi, 3)\n",
    "                    pl -= 1\n",
    "                    ph += 1\n",
    "                elif arr[ph] + arr[pl] > key:\n",
    "                    pl -= 1\n",
    "                else:\n",
    "                    ph += 1\n",
    "\n",
    "                if pl <= ph:\n",
    "                    break\n",
    "        # print(cache)\n",
    "        return maxi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 回想一下 第一题 Two Sum  -_-!!!!\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n, ret, dp = len(arr), 0, {}\n",
    "\n",
    "        for k in range(2, n):\n",
    "            i, j = 0, k - 1\n",
    "            while i < j:\n",
    "                # if arr[i] < arr[j]: break\n",
    "                tar = arr[i] + arr[j]\n",
    "                if tar == arr[k]:\n",
    "                    dp[(arr[j], arr[k])] = dp[(arr[i], arr[j])] + 1 if (arr[i], arr[j]) in dp else 3\n",
    "                    # ret = max(dp[(arr[j], arr[k])], ret)\n",
    "                    i += 1\n",
    "                    j -= 1\n",
    "                if tar < arr[k]: i += 1\n",
    "                if tar > arr[k]: j -= 1\n",
    "                       \n",
    "\n",
    "        return max(dp.values()) if len(dp) else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "            \n",
    "        res = 0\n",
    "\n",
    "        num_idx = dict()\n",
    "        for i, x in enumerate(arr):\n",
    "            num_idx[x] = i\n",
    "        \n",
    "        dp = defaultdict(lambda : 2)\n",
    "        for mid in range(n):\n",
    "            y = arr[mid]\n",
    "            for r in range(mid + 1, n):\n",
    "                z = arr[r]\n",
    "                x = z - y\n",
    "                if x in num_idx:\n",
    "                    l = num_idx[x]\n",
    "                    if l < mid:\n",
    "                        ID1 = l * n + mid\n",
    "                        ID2 = mid * n + r\n",
    "                        dp[ID2] = dp[ID1] + 1\n",
    "                        if dp[ID2] >= 3:\n",
    "                            res = max(res, dp[ID2])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        cache = [[] for i in range(len(arr))]\n",
    "        maxi = 0\n",
    "        for i in range(2, len(arr)):\n",
    "            key = arr[i]\n",
    "            ph = 0\n",
    "            pl = i-1\n",
    "            for j in range(i):\n",
    "                if arr[ph] + arr[pl] == key:\n",
    "                    flag = True\n",
    "                    for l in range(len(cache[pl])):\n",
    "                        if cache[pl][l][0] == arr[ph]:\n",
    "                            cache[i].append([arr[pl], cache[pl][l][1]+1])\n",
    "                            maxi = max(maxi, cache[pl][l][1]+1)\n",
    "                            flag = False\n",
    "                            break\n",
    "                    if flag:\n",
    "                        cache[i].append([arr[pl], 3])\n",
    "                        maxi = max(maxi, 3)\n",
    "                    pl -= 1\n",
    "                    ph += 1\n",
    "                elif arr[ph] + arr[pl] > key:\n",
    "                    pl -= 1\n",
    "                else:\n",
    "                    ph += 1\n",
    "\n",
    "                if pl <= ph:\n",
    "                    break\n",
    "        print(cache)\n",
    "        return maxi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        def dfs(i, j):\n",
    "            target = arr[i] + arr[j]\n",
    "            k = bisect_left(arr, target)\n",
    "            if k >= n or arr[k] != target:\n",
    "                return 0\n",
    "            return dfs(j, k) + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for ii in range(n):\n",
    "            for jj in range(ii + 1, n):\n",
    "                length = dfs(ii, jj) + 2\n",
    "                ans = max(ans, length)\n",
    "        \n",
    "        return ans if ans >= 3 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        arr1=set(arr)\n",
    "        res=0\n",
    "        n=len(arr)\n",
    "        def dfs(i,zhan):\n",
    "            nonlocal res\n",
    "            if len(zhan)>=3:\n",
    "                res=max(len(zhan),res)\n",
    "            if i>n-1:\n",
    "                return\n",
    "            if not zhan:\n",
    "                dfs(i+1,zhan)\n",
    "                zhan.append(arr[i])\n",
    "                dfs(i+1,zhan)\n",
    "                zhan.pop()\n",
    "            elif len(zhan)==1:\n",
    "                cur=arr[i]+zhan[-1]\n",
    "                if cur in arr1:\n",
    "                 zhan=zhan+[arr[i],cur]\n",
    "                 nex=arr.index(cur)+1\n",
    "                 dfs(nex,zhan)\n",
    "                 zhan=zhan[0:len(zhan)-2]\n",
    "                dfs(i+1,zhan)\n",
    "            else:\n",
    "                b=zhan[-1]+zhan[-2]\n",
    "                if b in arr1:\n",
    "                    zhan.append(b)\n",
    "                    nex=arr.index(b)+1\n",
    "                    dfs(nex,zhan)\n",
    "                    zhan.pop()\n",
    "        dfs(0,[])\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        arr1=set(arr)\n",
    "        res=0\n",
    "        n=len(arr)\n",
    "        def dfs(i,zhan):\n",
    "            nonlocal res\n",
    "            if len(zhan)>=3:\n",
    "                print(zhan)\n",
    "                res=max(len(zhan),res)\n",
    "            if i>n-1:\n",
    "                return\n",
    "            if not zhan:\n",
    "                dfs(i+1,zhan)\n",
    "                zhan.append(arr[i])\n",
    "                dfs(i+1,zhan)\n",
    "                zhan.pop()\n",
    "            elif len(zhan)==1:\n",
    "                cur=arr[i]+zhan[-1]\n",
    "                if cur in arr1:\n",
    "                 zhan.append(arr[i])\n",
    "                 zhan.append(cur)\n",
    "                 nex=arr.index(cur)+1\n",
    "                 dfs(nex,zhan)\n",
    "                 zhan.pop()\n",
    "                 zhan.pop()\n",
    "                dfs(i+1,zhan)\n",
    "            else:\n",
    "                b=zhan[-1]+zhan[-2]\n",
    "                if b in arr1:\n",
    "                    zhan.append(b)\n",
    "                    nex=arr.index(b)+1\n",
    "                    dfs(nex,zhan)\n",
    "                    zhan.pop()\n",
    "        dfs(0,[])\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        arr1=set(arr)\n",
    "        res=0\n",
    "        n=len(arr)\n",
    "        def dfs(i,zhan):\n",
    "            nonlocal res\n",
    "            if len(zhan)>=3:\n",
    "                res=max(len(zhan),res)\n",
    "            if i>n-1:\n",
    "                return\n",
    "            if not zhan:\n",
    "                dfs(i+1,zhan)\n",
    "                zhan.append(arr[i])\n",
    "                dfs(i+1,zhan)\n",
    "                zhan.pop()\n",
    "            elif len(zhan)==1:\n",
    "                cur=arr[i]+zhan[-1]\n",
    "                if cur in arr1:\n",
    "                 zhan.append(arr[i])\n",
    "                 zhan.append(cur)\n",
    "                 nex=arr.index(cur)+1\n",
    "                 dfs(nex,zhan)\n",
    "                 zhan.pop()\n",
    "                 zhan.pop()\n",
    "                dfs(i+1,zhan)\n",
    "            else:\n",
    "                b=zhan[-1]+zhan[-2]\n",
    "                if b in arr1:\n",
    "                    zhan.append(b)\n",
    "                    nex=arr.index(b)+1\n",
    "                    dfs(nex,zhan)\n",
    "                    zhan.pop()\n",
    "        dfs(0,[])\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr) -> int:\n",
    "        dic = {x:i for i, x in enumerate(arr)}\n",
    "\n",
    "        def recall(t):\n",
    "            if t not in dic:\n",
    "                return\n",
    "\n",
    "            path.append(t)\n",
    "            recall(path[-1] + path[-2])\n",
    "\n",
    "        ret = []\n",
    "        path = []\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i + 1, len(arr)):\n",
    "                path = [arr[i], arr[j]]\n",
    "                recall(path[-2] + path[-1])\n",
    "                if len(path) > len(ret) and len(path) > 2:\n",
    "                    ret = path[:]\n",
    "\n",
    "        return len(ret)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 动态规划，斐波那契数列的状态由最后两个元素决定\n",
    "    def lenLongestFibSubseq1(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        record = {}\n",
    "        # dp[i][j] 表示以 arr[i], arr[j] 为结尾的 j 状态下的最长斐波那契序列长度\n",
    "        dp = [[2]*n for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                before = arr[j] - arr[i]\n",
    "                if before in record:\n",
    "                    dp[i][j] = max(dp[i][j], dp[record[before]][i] + 1)\n",
    "                    ans = max(ans, dp[i][j])\n",
    "\n",
    "            record[arr[i]] = i\n",
    "\n",
    "        return ans if ans > 2 else 0\n",
    "\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        self.dic = dict()\n",
    "        for i,e in enumerate(arr):\n",
    "            self.dic[e] = i\n",
    "        def dfs(first,second,cnt):\n",
    "            if first+second in self.dic:\n",
    "                self.ans = max(self.ans,cnt+1)\n",
    "                dfs(second,first+second,cnt+1)\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i+1,len(arr)):\n",
    "                if arr[i]+arr[j] in self.dic:\n",
    "                    dfs(arr[i],arr[j],2)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        res = 0\n",
    "\n",
    "        def process(n1, n2, r):\n",
    "            nonlocal res\n",
    "            target = n1 + n2\n",
    "            if target in map:\n",
    "                process(n2, target, r + 1)\n",
    "            else:\n",
    "                res = max(res, r)\n",
    "\n",
    "        map = {elem: ind for ind, elem in enumerate(arr)}\n",
    "        lens = len(arr)\n",
    "        for i in range(lens):\n",
    "            for j in range(i):\n",
    "                if arr[i] + arr[j] in map:\n",
    "                    process(arr[j], arr[i], 2)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        def dfs(a:int,b:int)->int:\n",
    "            if a+b in setA:\n",
    "                return dfs(b,a+b)+1\n",
    "            return 0\n",
    "        \n",
    "        n=len(arr)\n",
    "        setA=set(arr)\n",
    "        res=0\n",
    "        for i in range(n-2):\n",
    "            for j in range(i+1,n-1):\n",
    "                res=max(dfs(arr[i],arr[j]),res)\n",
    "        \n",
    "        return (res+2) if res>0 else 0\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        #dp[i] = (dp[i-1], dp[i-1]+1)\n",
    "        location = {arr[i]:i for i in range(len(arr))}\n",
    "        \n",
    "        cache = set()\n",
    "        def dfs(x, y):\n",
    "            if x+y in location:\n",
    "                return 1 + dfs(y, x+y)\n",
    "            else:\n",
    "                return 0\n",
    "        \n",
    "        r = 0\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i+1, len(arr)):\n",
    "                if (arr[i], arr[j]) in cache:\n",
    "                    continue\n",
    "                if arr[i]+arr[j] in location:\n",
    "                    r = max(r, 2+dfs(arr[i], arr[j]))  \n",
    "        return r\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        hashmap = {}\n",
    "        for i in range(n):\n",
    "            hashmap[arr[i]] = i\n",
    "        cache = {}\n",
    "\n",
    "        def lenLongestFibSubseqCertainEnd(i, j):\n",
    "            if (i, j) in cache:\n",
    "                return cache[(i, j)]\n",
    "            if j <= i:\n",
    "                return 0\n",
    "            num = arr[j] - arr[i]\n",
    "            if num not in hashmap:\n",
    "                return 0\n",
    "            idx = hashmap[num]\n",
    "            if idx >= i:\n",
    "                return 0\n",
    "            cache[(i, j)] = lenLongestFibSubseqCertainEnd(idx, i) + 1\n",
    "            return cache[(i, j)]\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                res = max(res, lenLongestFibSubseqCertainEnd(i, j))\n",
    "        if res != 0:\n",
    "            return res + 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        length = len(arr)\n",
    "        dp = [0]*length\n",
    "        string = [[]]*length\n",
    "        max_length = 0\n",
    "        for i in range(2,length):\n",
    "            if i==2:\n",
    "                dp[2] = 3 if arr[0]+arr[1]==arr[2] else 0\n",
    "                string[2] = [[arr[0],arr[1],arr[2]]] if arr[0]+arr[1]==arr[2] else []\n",
    "                max_length = max(max_length,dp[2])\n",
    "            else:\n",
    "                now_result = []\n",
    "                now_length = 0\n",
    "                for j in range(2,i):#如果前面j个里有满足条件的\n",
    "                    if dp[j]==0:\n",
    "                        continue\n",
    "                    else:\n",
    "                        for now_str in string[j]:\n",
    "                            if now_str[-2]+now_str[-1]== arr[i]:\n",
    "                                now_result.append(now_str+[arr[i]])\n",
    "                                max_length = max(max_length,len(now_result[-1]))\n",
    "                                dp[i]+=1\n",
    "                l,r = 0,i-1\n",
    "                while(l<r):\n",
    "                    if arr[l]+arr[r] == arr[i]:\n",
    "                        now_result.append([arr[l],arr[r],arr[i]])\n",
    "                        max_length = max(max_length,len(now_result[-1]))\n",
    "                        dp[i]+=1\n",
    "                        l+=1\n",
    "                        r-=1\n",
    "                    elif arr[l]+arr[r] > arr[i]:\n",
    "                        r-=1\n",
    "                    else:\n",
    "                        l+=1\n",
    "                string[i] = now_result\n",
    "        return max_length\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n,Map=len(arr),{}\n",
    "        dp=[[2]*i for i in range(n)]\n",
    "        for i in range(n):\n",
    "            Map[arr[i]]=i\n",
    "        i=2\n",
    "        while i<n:\n",
    "            for j in range(i):\n",
    "                dp[i][j] = dp[j][Map[arr[i]-arr[j]]]+1 if arr[i]-arr[j] in Map and Map[arr[i]-arr[j]]<j  else 2\n",
    "            i+=1\n",
    "        ans=max([max(d) for d in dp if d])\n",
    "        return ans if ans>2 else 0\n",
    "\"\"\"\n",
    "哈西表+dp\n",
    "哈西表用于标记一个数的位置\n",
    "假设dp[n][m]表示以第n个数和第m个数为结尾的斐波那契数列的长度，m<n\n",
    "则dp[n][m]=dp[m][Map[arr[n]-arr[m]]] if arr[n]-arr[m] in Map and Map[arr[n]-arr[m]]<m else 2\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        mp = {}\n",
    "        for a in range(n):\n",
    "            mp[arr[a]] = a\n",
    "        dp = []\n",
    "        ans = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            dpRow = [2] * i\n",
    "            for j in range(i):\n",
    "                x = arr[i] - arr[j]\n",
    "                if x in mp and mp[x] < j:\n",
    "                    dpRow[j] = dp[j][mp[x]] + 1\n",
    "                    ans = max(ans, dpRow[j])\n",
    "            dp.append(dpRow)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        indices = {number: index for index, number in enumerate(arr)}\n",
    "\n",
    "        def dfs(i, j):\n",
    "            target = arr[i] + arr[j]\n",
    "            if target not in indices:\n",
    "                return 0\n",
    "            return dfs(j, indices[target]) + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for ii in range(len(arr)):\n",
    "            for jj in range(ii + 1, len(arr)):\n",
    "                length = dfs(ii, jj) + 2\n",
    "                ans = max(ans, length)\n",
    "        \n",
    "        return ans if ans >= 3 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        dp = [[0] * i for i in range(len(arr))]\n",
    "        for i, n in enumerate(arr):\n",
    "            j = i - 1\n",
    "            k = 0\n",
    "            while k < j:\n",
    "                diff = arr[i] - arr[j]\n",
    "                if diff == arr[k]:\n",
    "                    dp[i][j] = max(dp[i][j], 3, dp[j][k] + 1)\n",
    "                    ans = max(ans, dp[i][j])\n",
    "                    k += 1\n",
    "                    j -= 1\n",
    "                elif diff < arr[k]:\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    k += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        def dynamicPlan(lst):\n",
    "            n = len(lst)\n",
    "            lst_d = {lst[i]:i for i in range(n)}\n",
    "            f = []\n",
    "            for i in range(n):\n",
    "                f.append([])\n",
    "                for j in range(i + 1):\n",
    "                    f[-1].append(0)\n",
    "            result = 0\n",
    "            for i in range(2, n):\n",
    "                for j in range(i):\n",
    "                    k = lst_d.get(lst[i] - lst[j], -1)\n",
    "                    if k > -1 and k < j:\n",
    "                        f[i][j] = f[j][k] + 1\n",
    "                        result = max(result, f[i][j])\n",
    "            return result + 2 if result > 0 else 0\n",
    "        return dynamicPlan(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        dp_arr = [[]]\n",
    "        find_map = {}\n",
    "        for index, i in enumerate(arr):\n",
    "            find_map[i] = index\n",
    "        for i in range(1, len(arr), 1):\n",
    "            temp_arr = []\n",
    "            for j in range(0, i, 1):\n",
    "                temp_arr.append(2)\n",
    "            dp_arr.append(temp_arr)\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(1, len(arr), 1):\n",
    "            for j in range(0, i, 1):\n",
    "                if (arr[i]-arr[j]) in find_map.keys():\n",
    "                    index = find_map[arr[i]-arr[j]]\n",
    "                    if index < j:\n",
    "                        dp_arr[i][j] = max(dp_arr[i][j], dp_arr[j][index]+1)\n",
    "                        ans = max(ans, dp_arr[i][j])\n",
    "                    else:\n",
    "                        continue\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        s=set(arr)\n",
    "        index={}\n",
    "        for i in range(len(arr)):\n",
    "            index[arr[i]]=i\n",
    "        n=len(arr)\n",
    "        dp=[]\n",
    "        for i in range(n):\n",
    "            dp.append([])\n",
    "            for j in range(i):\n",
    "                dp[-1].append(0)\n",
    "        for i in range(2,n):\n",
    "            ans=0\n",
    "            for j in range(i):\n",
    "                if arr[j]*2<=arr[i]:\n",
    "                    continue\n",
    "                if arr[i]-arr[j] in s:\n",
    "                    ind=index[arr[i]-arr[j]]\n",
    "                    if dp[j][ind]==0:\n",
    "                        dp[i][j]=3\n",
    "                    else:\n",
    "                        dp[i][j]=dp[j][ind]+1\n",
    "        return max([max(dp[i]) for i in range(1,n)])\n",
    "        \n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        s=set(arr)\n",
    "        index={}\n",
    "        for i in range(len(arr)):\n",
    "            index[arr[i]]=i\n",
    "        n=len(arr)\n",
    "        dp=[]\n",
    "        for i in range(n):\n",
    "            dp.append([])\n",
    "            for j in range(i):\n",
    "                dp[-1].append(0)\n",
    "        for i in range(2,n):\n",
    "            ans=0\n",
    "            for j in range(i):\n",
    "                if arr[j]*2<=arr[i]:\n",
    "                    continue\n",
    "                if arr[i]-arr[j] in s:\n",
    "                    ind=index[arr[i]-arr[j]]\n",
    "                    if dp[j][ind]==0:\n",
    "                        dp[i][j]=3\n",
    "                    else:\n",
    "                        dp[i][j]=dp[j][ind]+1\n",
    "        #return dp\n",
    "        return max([max(dp[i]) for i in range(1,n)])\n",
    "        #return max(dp[-1])\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        indices = {x: i for i, x in enumerate(arr)}\n",
    "        ans, n = 0, len(arr)\n",
    "        dp = [[0] * _ for _ in range(n)]\n",
    "        for i, x in enumerate(arr):\n",
    "            if i>1:\n",
    "                for j in range(i - 1, -1, -1):\n",
    "                    if arr[j] * 2 <= x:\n",
    "                        break\n",
    "                    if x - arr[j] in indices:\n",
    "                        k = indices[x - arr[j]]\n",
    "                        dp[i][j] = max(dp[j][k] + 1, 3)\n",
    "                        ans = max(ans, dp[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        dic=collections.Counter(arr)\n",
    "        res=[]\n",
    "        max_arr=2\n",
    "        for i in range(n-1):\n",
    "            j=i+1\n",
    "            a,b = arr[i],arr[j]\n",
    "            while j <n:\n",
    "                c=a+b\n",
    "                if c in dic:\n",
    "                    max_arr+=1\n",
    "                    a,b=b,c\n",
    "                else:\n",
    "                    j+=1\n",
    "                    if j<n:\n",
    "                        a, b = arr[i], arr[j]\n",
    "                    res.append(max_arr)\n",
    "                    max_arr = 2\n",
    "        if max(res)==2:\n",
    "            return 0\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[2] * n for _ in range(n)]\n",
    "        dic = {}\n",
    "        for i in range(n):\n",
    "            dic[arr[i]] = i + 1\n",
    "        maxLen = 0\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                pre = arr[j] - arr[i]\n",
    "                numIndex = dic.get(pre)\n",
    "                if numIndex and numIndex - 1 < i:\n",
    "                    dp[i][j] = dp[numIndex - 1][i] + 1\n",
    "                    maxLen = max(maxLen, dp[i][j])\n",
    "        return maxLen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        s=set(arr)\n",
    "        d={}\n",
    "        m=len(arr)\n",
    "        for i in range(m):\n",
    "            d[arr[i]]=i\n",
    "        ma=0\n",
    "        c=[[2]*m for _ in range(m)]\n",
    "        for i in range(m-1):\n",
    "            for j in range(i+1,m):\n",
    "                if arr[i]+arr[j] in s:\n",
    "                    c[j][d[arr[i]+arr[j]]]=c[i][j]+1\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                ma=max(ma,c[i][j])\n",
    "        return ma if ma>2 else 0\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        indices = {x: i for i, x in enumerate(arr)}\n",
    "        n = len(arr)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if arr[j] * 2 <= x:\n",
    "                    break\n",
    "                if (x - arr[j]) in indices:\n",
    "                    k = indices[(x - arr[j])]\n",
    "                    dp[j][i] = max(dp[k][j] + 1, 3)\n",
    "                    ans = max(ans, dp[j][i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [ [0] * n for _ in range(n)]\n",
    "        res = 0\n",
    "        for i in range(2, n):\n",
    "            begin = 0\n",
    "            end = i - 1\n",
    "            while begin < end:\n",
    "                s = arr[begin] + arr[end]\n",
    "                if s < arr[i]:\n",
    "                    begin += 1\n",
    "                elif s > arr[i]:\n",
    "                    end -= 1\n",
    "                else:\n",
    "                    dp[end][i] = dp[begin][end] + 1\n",
    "                    begin += 1\n",
    "                    end -= 1\n",
    "        for i in range(1,n):\n",
    "            for j in range(i):\n",
    "                res = max(res, dp[j][i])\n",
    "        # print(dp)\n",
    "        return res if res == 0 else res + 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        indices = {x: i for i, x in enumerate(arr)}\n",
    "        ans, n = 0, len(arr)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i, x in enumerate(arr):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                if arr[j] * 2 <= x:\n",
    "                    break\n",
    "                if x - arr[j] in indices:\n",
    "                    k = indices[x - arr[j]]\n",
    "                    dp[j][i] = max(dp[k][j] + 1, 3)\n",
    "                    ans = max(ans, dp[j][i])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(arr)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        indices = {val: index for index, val in enumerate(arr)}\n",
    "        for i, x in enumerate(arr):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                j_val = arr[j]\n",
    "                if j_val * 2 <= x:\n",
    "                    break\n",
    "                k_val = x - j_val\n",
    "                if k_val in indices:\n",
    "                    k_index = indices[k_val]\n",
    "                    dp[j][i] = max(3, dp[k_index][j] + 1)\n",
    "                    ans = max(ans, dp[j][i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        indices = {x: i for i, x in enumerate(arr)}\n",
    "        ans, n = 0, len(arr)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i, x in enumerate(arr):\n",
    "            for j in range(i, -1, -1): # [n-1,-1)\n",
    "                if arr[j] * 2 <= x:\n",
    "                    break\n",
    "                if x - arr[j] in indices:\n",
    "                    k = indices[x - arr[j]]\n",
    "                    dp[j][i] = max(dp[k][j] + 1, 3)\n",
    "                    ans = max(ans, dp[j][i])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = []\n",
    "        index = {}\n",
    "        for i, v in enumerate(arr):\n",
    "            index[v] = i\n",
    "        \n",
    "        # for i in range(n-1, -1, -1):\n",
    "        #     sub = []\n",
    "        #     for j in range(0, i+1):\n",
    "        #         sub.append(0)\n",
    "        #     dp.append(sub)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        # print(dp)\n",
    "        ans = 0\n",
    "        for i, v in enumerate(arr):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if 2 * arr[j] > v:\n",
    "                    tmp = v - arr[j]\n",
    "                    if tmp in index:\n",
    "                        k = index[tmp]\n",
    "                        # print(f\"k: {k}, j: {j}, i: {i}\")\n",
    "                        # if k < j:\n",
    "                        dp[j][i] = max(dp[k][j] + 1, 3)\n",
    "                        ans = max(ans, dp[j][i])\n",
    "                else:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.d = {}\n",
    "\n",
    "    def func(self,i,j,mp):\n",
    "        if mp[i][j]==None:\n",
    "            return 2\n",
    "        else:\n",
    "            rr = self.d.get((i,j))\n",
    "            if rr!=None:\n",
    "                return rr\n",
    "            ret =  1 + self.func(j,mp[i][j],mp)\n",
    "            self.d[(i,j)] = ret\n",
    "            return ret\n",
    "\n",
    "    def binsearch(self,A,target,begin,end):\n",
    "        while True:\n",
    "            mid = (begin+end)//2\n",
    "            if mid==begin:\n",
    "                if A[begin]==target:\n",
    "                    return begin\n",
    "                elif A[end]==target:\n",
    "                    return end\n",
    "                else:\n",
    "                    return None\n",
    "            if A[mid]<target:\n",
    "                begin = mid\n",
    "            elif A[mid]>target:\n",
    "                end = mid\n",
    "            else:\n",
    "                return mid\n",
    "\n",
    "        \n",
    "\n",
    "    def lenLongestFibSubseq(self, A: List[int]) -> int:\n",
    "        d = {}\n",
    "        for i in range(len(A)):\n",
    "            d[A[i]] = i\n",
    "             \n",
    "        mp = []\n",
    "        for _ in range(len(A)):\n",
    "            mp.append([None]*len(A))\n",
    "\n",
    "        for i in range(0,len(A)-1):\n",
    "            for j in range(i+1,len(A)):\n",
    "                sm = A[i]+A[j]\n",
    "                mp[i][j] = d.get(sm)\n",
    "\n",
    "        #print(mp)\n",
    "\n",
    "        ret = 0\n",
    "        for i in range(0,len(A)-1):\n",
    "            for j in range(i+1,len(A)):\n",
    "                tmp = self.func(i,j,mp)\n",
    "                ret = max(ret,tmp)\n",
    "\n",
    "        if ret<3:\n",
    "            return 0\n",
    "        else:\n",
    "            return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        ans, n = 2, len(arr)\n",
    "        dic = {}\n",
    "        for index in range(len(arr)):\n",
    "            v = arr[index]\n",
    "            dic[v] = index\n",
    "\n",
    "        dp = [[0 for _ in range(len(arr))] for _ in range(len(arr))]\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            for j in range(i+1, len(arr)):\n",
    "                dp[i][j] = 2\n",
    "                v = arr[j] - arr[i]\n",
    "                if v in dic:\n",
    "                    dp[i][j] = max(dp[i][j], dp[dic[v]][i]+1)\n",
    "                ans = max(ans, dp[i][j])\n",
    "        return ans if ans > 2 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "\n",
    "        n, ans = len(arr), 2\n",
    "        if n <= 2: return 0\n",
    "\n",
    "        idx_map = dict() # 空间换时间，也可以用二分搜索做，因为序列是递增的\n",
    "        for i, num in enumerate(arr):\n",
    "            idx_map[num] = i\n",
    "\n",
    "        dp = [[0 for _ in range(n)] for __ in range(n)] # dp[i][j] -> 以arr[i], arr[j]为结尾的最长序列长度\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                dp[i][j], tar = 2, arr[j] - arr[i] # 长度至少是2\n",
    "                if tar in idx_map: # 前一个数在arr中\n",
    "                    dp[i][j] = max(2, dp[idx_map[tar]][i] + 1)\n",
    "                    ans = max(ans, dp[i][j])\n",
    "\n",
    "        return ans if ans > 2 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        indices = {x:i for i,x in enumerate(arr)}\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        dp = [[0 for i in range(n)] for j in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i,-1,-1):\n",
    "                if arr[j] * 2 <= arr[i]:\n",
    "                    break\n",
    "                if arr[i] - arr[j] in indices:\n",
    "                    k = indices[arr[i] - arr[j]]\n",
    "                    dp[j][i] = max(dp[k][j] + 1,3)\n",
    "                    ans = max(ans,dp[j][i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n,ans = len(arr),2\n",
    "        if n<=2: return 0\n",
    "        idxm = dict()\n",
    "        for i,num in enumerate(arr):\n",
    "            idxm[num] = i\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                dp[i][j],tar = 2,arr[j]-arr[i]\n",
    "                if tar in idxm:\n",
    "                    dp [i][j] = max(dp[i][j],dp[idxm[tar]][i]+1)\n",
    "                    ans = max(ans,dp[i][j])\n",
    "        return ans if ans>2 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        mp = {v:i for i,v in enumerate(arr)}\n",
    "        n = len(arr)\n",
    "        dp = [[0] *n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                dp[j][i] = 2\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                delta = arr[i]-arr[j]\n",
    "                if delta in mp:\n",
    "                    k = mp[delta]\n",
    "                    if k<j:\n",
    "                        dp[j][i] = dp[k][j]+1\n",
    "                        res = max(res, dp[j][i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr):\n",
    "        n = len(arr)\n",
    "        d = {c:i for i,c in enumerate(arr)}\n",
    "        ans = 0\n",
    "        dp=[[0]*n for _ in range(n)]\n",
    "        for i in range(2,n):\n",
    "            for j in range(i-1,0,-1):\n",
    "                tt = arr[i] - arr[j]\n",
    "                if tt in d:\n",
    "                    t = d[tt]\n",
    "                    if t < j:\n",
    "                        dp[i][j] = max(3,dp[j][t]+1)\n",
    "                        ans = max(ans,dp[i][j])\n",
    "                    else:\n",
    "                        break\n",
    "        return ans\n",
    "\n",
    "# arr = [1,3,7,11,12,14,18]\n",
    "# Solution().lenLongestFibSubseq(arr)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        dp = [[0] * len(arr) for _ in range(0, len(arr))]\n",
    "        result = 0\n",
    "        for i in range(2, len(arr)):\n",
    "            l = 0\n",
    "            r = i-1\n",
    "            while l < r:\n",
    "                if arr[l] + arr[r] == arr[i]:\n",
    "                    if dp[l][r] == 0:\n",
    "                        dp[r][i] = 3\n",
    "                    else:\n",
    "                        dp[r][i] = dp[l][r] + 1\n",
    "                    result = max(result, dp[r][i])\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "                elif arr[l] + arr[r] < arr[i]:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    r -= 1\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        indices = {x: i for i, x in enumerate(arr)}\n",
    "        ans, n = 0, len(arr)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i, x in enumerate(arr):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if arr[j] * 2 <= x:\n",
    "                    break\n",
    "                if x - arr[j] in indices:\n",
    "                    k = indices[x - arr[j]]\n",
    "                    dp[j][i] = max(dp[k][j] + 1, 3)\n",
    "                    ans = max(ans, dp[j][i])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        maxx = 0\n",
    "        indices = {x: i for i, x in enumerate(arr)}\n",
    "        for i in range(2,n):\n",
    "            for j in range(i):\n",
    "                diff = arr[i] - arr[j]\n",
    "                if diff in indices and indices[diff] < j:\n",
    "                    k = indices[diff]\n",
    "                    dp[i][j] = dp[j][k] + 3 if dp[j][k] == 0 else dp[j][k] + 1\n",
    "                    maxx = max(maxx,dp[i][j])\n",
    "                    print(i,j,k)\n",
    "        # for i in range(2, n):\n",
    "        #     for j in range(i):\n",
    "        #         if arr[i]\n",
    "            # j = i-1\n",
    "            # k = 0\n",
    "            # while k<j:\n",
    "            #     # print(i,j,k)\n",
    "            #     # print(arr[i],arr[j] ,arr[k])\n",
    "            #     if arr[i] == arr[j] + arr[k]:\n",
    "            #         dp[i][j] = dp[j][k] + 3 if dp[j][k] == 0 else dp[j][k] + 1\n",
    "            #         maxx = max(maxx,dp[i][j])\n",
    "            #         j -= 1\n",
    "            #         k += 1\n",
    "            #     elif arr[i] < arr[j] + arr[k]:\n",
    "            #         j -= 1\n",
    "            #     else:\n",
    "            #         k +=1\n",
    "\n",
    "\n",
    "        return maxx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        hash_map = {v:i for i,v in enumerate(arr)}\n",
    "\n",
    "        if n<=2:\n",
    "            return 0\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            target_2 = arr[i]\n",
    "            max_i = 0\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if arr[j]*2<=target_2:\n",
    "                    break\n",
    "                if target_2 - arr[j] in hash_map:\n",
    "                    target_0 = hash_map[target_2 - arr[j]]\n",
    "                    if target_0 >= j: continue\n",
    "                    dp[i][j] = max(dp[j][target_0] + 1, 3)\n",
    "        return max([max(l) for l in dp])\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, arr: List[int]) -> int:\n",
    "        l = len(arr)\n",
    "        dp = [[2 for j in range(l)] for i in range(l-1)]\n",
    "        max_ = 0\n",
    "        for i in range(2,l):\n",
    "            j = 0\n",
    "            k = i-1\n",
    "            while j < k:\n",
    "                s = arr[j] + arr[k]\n",
    "                if s == arr[i]:\n",
    "                    dp[k][i] = dp[j][k] + 1\n",
    "                    max_ = max(max_,dp[k][i])\n",
    "                    j += 1\n",
    "                    k -=1\n",
    "                \n",
    "                if s < arr[i]:\n",
    "                    j += 1\n",
    "                if s> arr[i]:\n",
    "                    k-=1\n",
    "        return max_ if max_ != 2 else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from pprint import pprint\n",
    "class Solution:\n",
    "    def lenLongestFibSubseq(self, a: List[int]) -> int:\n",
    "        n = len(a)\n",
    "        idxs  = list(range(n))\n",
    "        mp = dict(zip(a, idxs))# ele to idx\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        # i,j,k f(j,k) = f(i,j) + 1 where a[i]+a[j] = a[k]\n",
    "        dp[0][0] = 1\n",
    "        for k in range(1, n):\n",
    "            for j in range(0, k):\n",
    "                dp[j][k] = 2\n",
    "                if a[k] - a[j] in mp:\n",
    "                    i = mp[a[k]-a[j]]\n",
    "                    if i<j:\n",
    "                        dp[j][k] = dp[i][j] + 1\n",
    "        # pprint(dp)\n",
    "        longest = 2\n",
    "        for row in dp:\n",
    "            longest = max(longest, max(row))\n",
    "        if longest==2: \n",
    "            return 0\n",
    "        else:\n",
    "            return longest"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
